from collections import deque


class Graph:
    def __init__(self):
        self.graph_dict = {}

    def add_vertex(self, node):
        if node not in self.graph_dict:
            self.graph_dict[node] = []
        return self

    def add_edge(self, v1, v2):
        self.graph_dict[v1].append(v2)
        self.graph_dict[v2].append(v1)
        return self

    def bfs(self, start):
        visit = deque([start])     # 使用start初始化一个双端队列
        visited = [start]         # 存储访问过的节点
        while len(visit) > 0:      # 双端队列中含有元素
            v = visit.popleft()
            # visit.extend([i for i in self.graph_dict[v] if i not in visited and i not in visit])    # 将队列中不存在并且还未访问的节点加入队列
            for neighbor in self.graph_dict[v]:
                if neighbor not in visited:
                    visited.append(neighbor)
                    visit.append(neighbor)
        print(visited)
        return visited

    def bfs_not_connected(self, start):         # 处理非连通图的情况
        visited = self.bfs(start)
        need_visit = [i for i in self.graph_dict.keys() if i not in visited]
        while len(need_visit) > 0:
            visited = self.bfs(need_visit[0])
            need_visit = [i for i in need_visit if i not in visited]

    # 通过广度优先遍历查找两个节点之间的最短路径可以将相邻的两个节点都入队
    def __getPath(self, v):
        res = []
        for i in self.graph_dict[v]:
            pair = (v, i)
            res.append(pair)
        return res

    def bfs_route(self, start, end):           # 此算法仅能找到一条最短路径
        visited = deque(self.__getPath(start))
        visit = deque(self.__getPath(start))
        while len(visit) > 0:
            v = visit.popleft()
            if v[1] == end:
                break
            neighbor_edges = self.__getPath(v[1])
            for i in neighbor_edges:
                if i not in visited and (i[1], i[0]) not in visited:
                    visited.append(i)
                    visit.append(i)
        end_edge = visited.pop()
        if end_edge[1] != end:
            return None
        path = deque([end_edge[0], end])
        pre = end_edge[0]
        while len(visited) > 0:
            edge = visited.pop()
            if edge[1] != pre:
                continue
            pre = edge[0]
            path.appendleft(pre)
        return list(path)


